import javax.xml.soap.Node;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 模拟实现二叉树的功能
 */
public class MyBinaryTree {
    //树的节点
    public class Node {
        private int val;//数据
        private Node left;//左孩子
        private Node right;//右孩子
        private Node(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "节点=" + val +
                    ", 左子节点=" + left.val +
                    ", 右子节点=" + right.val +
                    '}';
        }
    }

    //构造一棵二叉树
    public Node createBinaryTree() {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;

        return node1;
    }

    //判断二叉树是否为空
    public boolean isEmpty(Node root) {
        return root == null;
    }

    //前序遍历
    public void preOrder(Node root) {
        if (isEmpty(root)) {
            return;
        }
        //节点不为空，打印val值
        System.out.print(root.val+" ");
        //访问左子树
        preOrder(root.left);
        //访问右子树
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(Node root) {
        if (isEmpty(root)) {
            return;
        }
        //先访问左子树
        inOrder(root.left);
        //当左子树遍历完，返回时打印val值
        System.out.print(root.val+" ");
        //再访问右子树
        inOrder(root.right);
    }

    //后序遍历
    public void postOrder(Node root) {
        if (isEmpty(root)) {
            return;
        }
        //先访问左子树
        inOrder(root.left);
        //再访问右子树
        inOrder(root.right);
        //当左子树和右子树都访问完后打印val
        System.out.print(root.val+" ");
    }

    // 获取树中节点的个数
    public int size(Node root) {
        if(isEmpty(root)) {
            return 0;
        }
        //将遍历的左子树右子树加起来，然后再加上本身的一个节点
        return size(root.left) + size(root.right) + 1;
    }

    // 获取叶子节点的个数
    public int getLeafNodeCount(Node root) {
        if (isEmpty(root)) {
            return 0;
        }
        //如果一个节点的左子树和右子树都为null，说明这个节点就是叶子节点
        if (root.left == null && root.right == null) {
            return 1;
        }
        //将返回的叶子节点加起来
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    // 获取第K层节点的个数
    public int getKLevelNodeCount(Node root,int k) {
        if (isEmpty(root)) {
            return 0;
        }
        //当k=1时，就是我们要获取的第k层的节点个数
        if (k == 1) {
            return 1;
        }
        //递归到第k层
        return getKLevelNodeCount(root.left, k - 1)
                + getKLevelNodeCount(root.right, k - 1);
    }

    // 获取二叉树的高度
    public int getHeight(Node root) {
        if (isEmpty(root)) {
            return 0;
        }
        //遍历左子树
        int left = getHeight(root.left);
        //遍历右子树
        int right = getHeight(root.right);
        //判断左子树和右子树谁的节点多，多的子树加上本节点返回给上一层
        return left >= right ? left+1 : right+1;
    }

    // 检测值为value的元素是否存在
    public Node find(Node root, int val) {
        if (isEmpty(root)) {
            return null;
        }
        //当元素存在直接返回这个元素的节点
        if (root.val == val) {
            return root;
        }
        //访问左子树
        Node nodeL = find(root.left,val);
        if (nodeL != null) {
            return nodeL;
        }
        //访问右子树
        Node nodeR = find(root.right,val);
        if (nodeR != null) {
            return nodeR;
        }
        //如果没有这个节点就返回null
        return null;
    }

    //层序遍历
    public void levelOrder(Node root) {
        if(isEmpty(root)) {
            return;
        }
        //用队列存储节点
        Queue<Node> queue = new LinkedList<>();
        //将第一个节点放入队列中
        queue.offer(root);
        //当队列不为空，就进入循环
        while (!queue.isEmpty()) {
            //弹出队列的队头元素
            Node tmp = queue.poll();
            //打印队头元素的值
            System.out.print(tmp.val+" ");
            //如果弹出的这个元素的左节点不为空，就入队列
            if (!isEmpty(tmp.left)) {
                queue.offer(tmp.left);
            }
            //如果弹出的这个元素的右节点不为空，就入队列
            if (!isEmpty(tmp.right)) {
                queue.offer(tmp.right);
            }
        }
        System.out.println();
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(Node root) {
        if (isEmpty(root)) {
            return true;
        }
        //用队列存储节点
        Queue<Node> queue = new LinkedList<>();
        //将第一个节点放入队列中
        queue.offer(root);
        //队列不为空，进循环
        while (!queue.isEmpty()) {
            //弹出队列的队头节点
            Node tmp = queue.poll();
            /*
            判断弹出的节点是否为null，如果是则将队列中的节点挨个弹出，并判断弹出的节点是否都为null，
            如果有一个不为null则就不是完成二叉树，直接返回false.
            如果弹出的节点不为null，则将这个节点的左右节点都入队。
            当队列为空，不进入循环是则为完全二叉树返回true
             */
            if (tmp == null) {
                while (!queue.isEmpty()) {
                    Node t = queue.poll();
                    if (t != null) {
                        return false;
                    }
                }
            } else {
                queue.offer(tmp.left);
                queue.offer(tmp.right);
            }
        }
        return true;
    }
}